CAD systems are widely used in the design of mechanical or electronic parts or other objects and there are several commercially available systems of that type. A common characteristic of these systems is that the objects are designed by the user in an interactive mode. That means that the object is displayed on a screen as far as it has been designed by the user and the user can enter commands to apply modifications and/or additions to the already existing structure.
For displaying the geometric object under design, typically a cathode ray tube (CRT) or a liquid crystal display (LCD) is used. The object is displayed in an isometric view, whereby it can additionally be illuminated by computer generated light sources to yield realistic three-dimensional images. The commands for supplementing or modifying the object are entered by a computer mouse, a graphics tablet, or a light pen. When the editing process is finished and the object to be designed has assumed its final shape, a hardcopy can be produced by a printer or plotter.
An example for a commercially available 3D CAD system is the Hewlett-Packard Precision Engineering Solid Designer Version 2.0. A description of a 3D CAD system is also known from I. C. Braid :"Notes on a geometric modeller", C.A.D. Group Document No. 101, University of Cambridge, June 1979. Another description of a 3D CAD system is known from the article by I. C. Braid et al.: "Stepwise Construction of Polyhedra in Geometric Modelling", in K. W. Brodlie (Ed.): "Mathematical Methods in Computer Graphics and Design", Academic Press, 1980.
In the meantime, several CAD systems have been developed, for example the above mentioned system by Hewlett-Packard, which have the capability to perform Boolean operations like UNITE, SUBTRACT, or INTERSECT on geometric objects. In order to be able to create a wide range of complex objects, solid modellers must robustly support Boolean operations. Existing CAD systems, however, are not satisfactory in all respects since they are not able to perform Boolean operations with all desirable geometric configurations. In particular tangential or almost tangential geometries where a shallow intersection of surfaces has to be performed for executing the Boolean operation introduce numerical inconsistencies large enough to make the operation fail. Due to such errors in the calculation of intersections, the CAD system either produces an error message that it cannot execute the operation or the geometric object resulting from the operation does not have the shape which it should have in the ideal situation. The mentioned problems also occur with partially coincident geometries where edges of a face of the geometric object and intersection lines between a surface containing this face and another surface containing a face of the other geometric object are nearly coincident.
As already mentioned, the computation of the boundary of a solid which is defined as the result of a Boolean operation requires algorithms for surface/surface intersections, for curve/surface intersections, and for curve/curve intersections. To yield a sound boundary, these intersections must be consistent to a degree determined by the resolution of the model. The resolution specifies the allowable error (epsilon) that can be tolerated before the model "falls apart". For example, a curve is still considered to lie in a specific surface if it is not more than epsilon away from the surface, and three edges which miss each other by less than epsilon are still considered to intersect at a common vertex. An important step in the calculation of the boundary of a solid (e.g., the result of a Boolean operation) is the construction of the intersection graph which describes a segment of a surface/surface intersection track that is inside both intersecting faces. In connection with the construction of the intersection graph, it may occur that intersection points which should ideally be coincident with the intersection track are more than epsilon apart so that no consistent geometric object can be constructed, i.e., the model falls apart.
There are two methods usually employed to cope with the mentioned problems:
1. Numerical methods to increase the accuracy of curve/surface intersections. This approach is only applicable for very special combinations of curves and surfaces. The corresponding algorithms are comparatively slow and still do not return reliable results in numerically ill defined situations. PA0 2. Methods using curve/curve intersections instead of curve/surface intersections. The disadvantage of such methods is that curve/curve intersections are numerically less stable than curve/surface intersections, because three-dimensional curves hardly ever meet at a common point due to the limited numerical resolution.